#include <stdlib.h>
#include <stdio.h>
typedef int ElemType;
// 定义二叉树的结构
typedef struct BNode {
    ElemType data;// 数据
    struct BNode *lchild, *rchild;// 左孩子、右孩子
} BNode, *BTree;

// 二叉排序树的插入
int BST_Insert(BTree &T, ElemType e) {
    if (T == NULL) {
        // 为第一个结点申请空间，第一个结点作为树根，后面再进入的则是叶子结点
        T = (BNode *) malloc(sizeof(BNode));
        T->data = e;
        T->lchild = T->rchild = NULL;
        return 1; // 插入成功
    } else if (e == T->data) {
        return 0; // 相同元素，不可插入
    } else if (e < T->data) {
        // 插入的元素小于当前结点，则插入到左孩子
        return BST_Insert(T->lchild, e);
    } else {
        // 插入的元素大于当前结点，插入到右孩子
        return BST_Insert(T->rchild, e);
    }
}

// 创建二叉排序树
void Create_BST(BTree &T, ElemType elem[], int length) {
    T = NULL; // T是树跟
    for (int i = 0; i < length; i++) {
        BST_Insert(T, elem[i]);
    }
}

// 二叉排序树的查找
BTree BST_Search(BTree T, ElemType elem) {
    BTree p = T;
    while (p != NULL && p->data != elem) {
        if (elem > p->data) {
            // 查找的元素比当前结点大，则去右边查找
            p = p->rchild;
        } else {
            // 查找的元素比当前结点小，则去左边查找
            p = p->lchild;
        }
    }
    return p;
}
// 二叉排序树的删除
void DeleteNode(BTree &root,ElemType elem){
    if(root == NULL) return;
    if(elem < root->data){
        // 删除左子树
        DeleteNode(root->lchild,elem);
    }else if(elem > root->data){
        // 删除右子树
        DeleteNode(root->rchild,elem);
    }else{
        // 找到了要删除的结点
        if(root->lchild == NULL){ // 左子树为空，则右子树直接顶上去
            BTree tmp = root;
            root = root->rchild;
            free(tmp);
        } else if(root->rchild == NULL){ // 右子树为空，则左子树顶上去
            BTree tmp = root;
            root = root -> lchild;
            free(tmp);
        }else{
            // 左右子树都不为空。
            // 一般的删除策略：左子树的最大数据或右子树的最小数据代替
            BTree  tmp = root -> lchild; // 此处用左子树的最大数据代替
            while(tmp->rchild != NULL){ // 循环遍历，找到左子树的最大数据
                tmp = tmp->rchild;
            }
            root->data = tmp->data; // 将要删除结点上的数据替换掉
            DeleteNode(root->lchild,tmp->data);
        }
    }
}

int main() {
    BTree T;
    ElemType elem[7] = {54, 20, 66, 40, 28, 79, 58};
    // 创建二叉排序树
    Create_BST(T, elem, 7);

    // 二叉排序树的查找
    BTree B = BST_Search(T, 40);
    if (B != NULL) {
        printf("find node,value = %d\n", B->data);
    } else {
        printf("find failed\n");
    }
    return 0;
}
